package com.algorithm.recursion;

import java.util.Arrays;

/**
 * 多路递归
 */
public class E01Fibonacci {

    /**
     * 使用 Memoization(记忆法，也称备忘录)改进
     */
    public static int fibonacci(int n) {
        if(n==0){
            return 0;
        }
        int[] cache = new int[n + 1];
        Arrays.fill(cache,-1);
        cache[0]=0;
        cache[1]=1;
        return f(n, cache);
    }

    /**
     * 递归求斐波那契第n项
     * 会出现爆栈问题（解决方法：递归改循环或用其他语言如scala实现尾递归）
     */
    public static int f(int n,int[] cache){
        /*if (n==0) {
            return 0;
        }
        if (n==1) {
            return 1;
        }*/
        if (cache[n] != -1) {
            return cache[n];
        }
        cache[n] = f(n - 1, cache) + f(n - 2, cache);
        return cache[n];
    }
    public static int cal(int n){
        if (n==0|| n==1) {
            return n;
        }
        int a = 0,b=1,sum=0;
        for (int i = 2; i <=n; i++) {
            sum =a+b;
            a = b;
            b = sum;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(cal(6));
        System.out.println(fibonacci(5));
    }
}
